Comptage de chemins (graphe orienté) - Exemple

Prenons le graphe ci-dessous.

Sa matrice d'adjacence est  \(A=\begin {pmatrix} 0&0&1&0&1\\1&0&0&0&0\\0&1&0&1&0\\0&0&0&0&0\\0&0&1&1&0\end {pmatrix}\)

\(M=A^3=\begin {pmatrix} 1&1&0&1&0\\0&1&1&2&0\\0&0&1&0&1\\0&0&0&0&0\\1&0&0&0&0\end {pmatrix}\)

On lit donc (coefficient  \(m_{1,2}=1\) ) qu'il y a un chemin de 3 arcs qui va du sommet 1 au sommet 2 ; il s'agit du chemin 1 - 5 - 3 - 2.

En revanche, il n'y a aucun chemin de 2 arcs qui va du sommet 2 au sommet 1 (coefficient  \(m_{2,1}=0\) ).

On lit aussi   (coefficient  \(m_{2,4}=2\) ) qu'il y a deux chemins de 3 arcs qui vont du sommet 2 au sommet 4.

Il s'agit des chemins :

• 2 - 1 - 5 - 4
• 2 - 1 - 3 - 4

Remarques

• Comme le graphe est orienté, la matrice  \(A\)  n'est pas symétrique et aucune de ses puissances ne l'est.
• Aucun arc ne part du sommet 4, donc il n'existe aucune possibilité d'aller du sommet 4 à un autre sommet, quel que soit le nombre d'arcs envisagé.